/*
 * @lc app=leetcode.cn id=1631 lang=typescript
 *
 * [1631] 最小体力消耗路径
 */

// @lc code=start
interface Cell {
  x: number;
  y: number;
}

function minimumEffortPath(heights: number[][]): number {
  const m = heights.length;
  const n = heights[0].length;
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  // 当前的消耗是否可达终点
  const bfs = (cost: number): boolean => {
    const mark = new Array(m).fill(0).map(() => new Array(n).fill(0));
    const queue: Cell[] = [];
    queue.push({ x: 0, y: 0 });
    mark[0][0] = 1;
    while (queue.length) {
      const curr = queue.shift();
      if (curr.x === m - 1 && curr.y === n - 1) {
        return true;
      }
      for (const [x, y] of dirs) {
        const nx = curr.x + x;
        const ny = curr.y + y;
        if (nx < 0 || nx >= m || ny < 0 || ny >= n || mark[nx][ny] === 1) {
          continue;
        }
        if (Math.abs(heights[curr.x][curr.y] - heights[nx][ny]) <= cost) {
          queue.push({ x: nx, y: ny });
          mark[nx][ny] = 1;
        }
      }
    }
    return false;
  };
  // 二分查找最小消耗
  let l = 0;
  let r = 10 ** 6;
  while (l < r) {
    let mid = l + ((r - l) >> 1);
    if (bfs(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
}
// @lc code=end
